package com.learn.algorithm;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 设计并实现双端队列
 * https://leetcode.cn/problems/design-circular-deque/
 * https://leetcode.cn/problems/design-circular-queue/
 */
public class CircularDeque {

    static class MyCircularQueue {
        private final int[] deque;
        private int l, r, size;
        private final int limit;

        public MyCircularQueue(int k) {
            deque = new int[k];
            l = r = size = 0;
            limit = k;
        }

        public boolean enQueue(int value) {
            if (isFull()) {
                return false;
            } else {
                if (isEmpty()) {
                    l = r = 0;
                    deque[0] = value;
                } else {
                    r = r == limit - 1 ? 0 : r + 1;
                    deque[r] = value;
                }
                size++;
                return true;
            }
        }

        public boolean deQueue() {
            if (isEmpty()) {
                return false;
            } else {
                l = l == limit - 1 ? 0 : l + 1;
                size--;
                return true;
            }
        }

        public int Front() {
            if (isEmpty()) {
                return -1;
            } else {
                return deque[l];
            }
        }

        public int Rear() {
            if (isEmpty()) {
                return -1;
            } else {
                return deque[r];
            }
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return limit == size;
        }
    }

    static class MyCircularDeque {
        private final int[] deque;
        private int l, r, size;
        private final int limit;

        public MyCircularDeque(int k) {
            deque = new int[k];
            l = r = size = 0;
            limit = k;
        }

        public boolean insertFront(int value) {
            if (isFull()) {
                return false;
            } else {
                if (isEmpty()) {
                    l = r = 0;
                    deque[0] = value;
                } else {
                    l = l == 0 ? limit - 1 : l - 1;
                    deque[l] = value;
                }
                size++;
                return true;
            }
        }

        public boolean insertLast(int value) {
            if (isFull()) {
                return false;
            } else {
                if (isEmpty()) {
                    l = r = 0;
                    deque[0] = value;
                } else {
                    r = r == limit - 1 ? 0 : r + 1;
                    deque[r] = value;
                }
                size++;
                return true;
            }
        }

        public boolean deleteFront() {
            if (isEmpty()) {
                return false;
            } else {
                l = l == limit - 1 ? 0 : l + 1;
                size--;
                return true;
            }
        }

        public boolean deleteLast() {
            if (isEmpty()) {
                return false;
            } else {
                r = r == 0 ? limit - 1 : r - 1;
                size--;
                return true;
            }
        }

        public int getFront() {
            if (isEmpty()) {
                return -1;
            } else {
                return deque[l];
            }
        }

        public int getRear() {
            if (isEmpty()) {
                return -1;
            } else {
                return deque[r];
            }
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return limit == size;
        }
    }

    static class MyCircularDeque1 {
        private final Deque<Integer> deque;
        private int size;
        private final int limit;

        public MyCircularDeque1(int k) {
            deque = new LinkedList<>();
            size = 0;
            limit = k;
        }

        public boolean insertFront(int value) {
            if (isFull()) {
                return false;
            }
            size++;
            deque.offerFirst(value);
            return true;
        }

        public boolean insertLast(int value) {
            if (isFull()) {
                return false;
            }
            size++;
            deque.offerLast(value);
            return true;
        }

        public boolean deleteFront() {
            if (isEmpty()) {
                return false;
            }
            size--;
            deque.pollFirst();
            return true;
        }

        public boolean deleteLast() {
            if (isEmpty()) {
                return false;
            }
            size--;
            deque.pollLast();
            return true;
        }

        public int getFront() {
            if (isEmpty()) {
                return -1;
            } else {
                return deque.peekFirst();
            }
        }

        public int getRear() {
            if (isEmpty()) {
                return -1;
            } else {
                return deque.peekLast();
            }
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return limit == size;
        }
    }

    public static void main(String[] args) {
        MyCircularDeque c = new MyCircularDeque(3);
        c.insertLast(1);
        c.insertLast(2);
        c.insertFront(3);
        System.out.println(c.getRear());
    }
}
